#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
const int N = 2e6 + 10;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;
    int sumb = 0;
    int suma = 0;
    int ans = 0x3f3f3f3f3f3f3f3f3f;
    for(int i = 1; i <= n; i ++)
    {
        if(s[i] == 'a') suma ++;
        else sumb ++;
    }
    int sum = 0;
    int cntb = 0;
    int cnta = 0;
    // a          b         a
    cntb = 0;
    sum = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(s[i] == 'b') cntb ++;
        else 
        {
            sum += min(cntb,sumb - cntb);
        }
    }
    ans = min(ans,sum);
    cnta = 0;
    sum = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(s[i] == 'a') cnta ++;
        else 
        {
            sum += min(cnta,suma - cnta);
        }
    }
    ans = min(ans,sum);
    cout << ans << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--)
    {
        solve();
    }
}